package com.dataStructures.recursion;

public class MiGong {

	public static void main(String[] args) {

		// 创建迷宫
		int[][] map = new int[8][7];
		// 使用 1 表示墙
		// 上下设置为 1
		for (int i = 0; i < 7; i++) {
			map[0][i] = 1;
			map[7][i] = 1;
		}

		// 左右设置为 1
		for (int j = 0; j < 8; j++) {
			map[j][0] = 1;
			map[j][6] = 1;
		}

		// 设置挡板
		map[3][1] = 1;
		map[3][2] = 1;

		// 输出地图
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 7; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}

		setWay(map, 1, 1);

		// 输出地图
		System.out.println("小球走过，并标识过的 地图的情况");
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 7; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}

	/**
	 * map[i][j]: 0:没走过；1:墙；2:走过且通；3:走过不通
	 * 定制一个策略：比如 下 → 右 → 上 → 左
	 *
	 * @param map 地图
	 * @param i   开始位置
	 * @param j   开始位置
	 * @return 是否找到出口 （[6][5]位置说明找到）
	 */
	public static boolean setWay(int[][] map, int i, int j) {
		if (map[6][5] == 2) {
			return true;
		}
		if (map[i][j] == 0) {
			// 先假定改点可以走通
			map[i][j] = 2;
			if (setWay(map, i + 1, j)) {
				// 下
				return true;
			} else if (setWay(map, i, j + 1)) {
				// 右
				return true;
			} else if (setWay(map, i - 1, j)) {
				// 上
				return true;
			} else if (setWay(map, i, j - 1)) {
				// 左
				return false;
			} else {
				map[i][j] = 3;
				return false;
			}
		} else {
			return false;
		}
	}

}
